package com.sukaiyi.leetcode._5longest_palindromic_substring;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

/**
 * 最长回文子串
 * <p>
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000
 *
 * @author sukaiyi
 * @date 2020/04/30
 * @see <a href="https://leetcode-cn.com/problems/longest-palindromic-substring/">题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertTrue(Arrays.asList("234432").contains(longestPalindrome("12344323")));
        assertTrue(Arrays.asList("aba").contains(longestPalindrome("aba")));
        assertTrue(Arrays.asList("").contains(longestPalindrome("")));
        assertTrue(Arrays.asList("bb").contains(longestPalindrome("bb")));
        assertTrue(Arrays.asList("bab", "aba").contains(longestPalindrome("babad")));
        assertTrue(Arrays.asList("bb").contains(longestPalindrome("cbbd")));
    }


    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        int[] dp = new int[chars.length];
        int[] st = new int[chars.length];
        int maxIndex = 0;
        for (int i = 0; i < chars.length; i++) {
            if (i + 1 < chars.length && chars[i] == chars[i + 1]) {
                int j = 1;
                while (i - j >= 0 && i + 1 + j < chars.length && chars[i - j] == chars[i + 1 + j]) {
                    j++;
                }
                dp[i] = j * 2;
                st[i] = i - (j - 1);
            }

            int j = 1;
            while (i - j >= 0 && i + j < chars.length && chars[i - j] == chars[i + j]) {
                j++;
            }
            if (2 * j - 1 > dp[i]) {
                dp[i] = 2 * j - 1;
                st[i] = i - (j - 1);
            }

            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        return s.substring(st[maxIndex], st[maxIndex] + dp[maxIndex]);
    }

}
